Độ phức tạp của thuật toán là O(n)

Như đã thấy trong ví dụ ở trên, thuật toán mạnh hơn các thuật toán so khớp chuỗi kém hơn vì nó có thể bỏ qua các ký tự đã duyệt. Ít ô phải quay trở lại hơn, thuật toán sẽ nhanh hơn, và được thể hiện trong bảng T bởi sự hiện diện của các số không. Một từ như "ABCDEFG" sẽ làm tốt với thuật toán này vì nó không có sự lặp lại của những chữ bắt đầu, vì vậy mảng đơn giản chỉ toàn số không với -1 ở đầu. Ngược lại, với từ W = "AAAAAAA" nó hoạt động tồi tệ, bởi vì bảng sẽ là

Đây là mẫu xấu nhất cho mảng T, và nó có thể dùng để so sánh với đoạn như S = "AAAAAABAAAAAABAAAAAAA", trong trường hợp này thuật toán sẽ cố gắng ghép tất cả các chữ 'A' với 'B' trước khi dừng lại; kết quả là số lượng tối đa câu lệnh được sử dụng, tiến tới trên hai lần số ký tự của xâu S khi số lần lặp của "AAAAAAB" tăng. Mặc dù quá trình xây dựng bảng rất nhanh so với chữ này (nhưng vô tác dụng), quá trình này chạy có một lần với chữ W, trong khi quá trình tìm kiếm chạy rất nhiều lần. Nếu với mỗi lần, từ W được dùng để tìm trên xâu như xâu S, độ phức tạp tổng thể sẽ rất lớn. Bằng cách so sánh, sự kết hợp này là trường hợp tốt nhất với thuật toán so khớp chuỗi Boyer-Moore.

Lưu ý rằng trong thực tế, thuật toán KMP làm việc không tốt đối với tìm kiếm trong văn bản ngôn ngữ tự nhiên, bởi vì nó chỉ có thể bỏ qua các ký tự khi phần đầu của từ giống với một phần trong văn bản. Trong thực tế điều này chỉ đôi khi xảy ra trong các văn bản ngôn ngữ tự nhiên. Ví dụ, hãy xem xét bao nhiêu lần một xâu "text" xuất hiện trong đoạn văn này.